package com.ryujung.dfs_backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution46 {
    /**
     * 解答成功:
     * 	执行耗时:1 ms,击败了82.47% 的Java用户
     * 	内存消耗:41.8 MB,击败了40.32% 的Java用户
     *
     * 思路
     * 需要一个数组来记忆哪些数字已经在回溯过程中使用了，并传递给下一次dfs，
     * 确保不会重复选择已经使用的index。
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> ans = new ArrayDeque<>();
        boolean[] isHasUsedArr = new boolean[nums.length];
        dfs(nums, 0, isHasUsedArr, ans, res);
        return res;
    }

    // 1,2,2,3
    private void dfs(int[] nums, int index, boolean[] isHasUsedArr, Deque<Integer> ans, List<List<Integer>> res) {
        if (index == nums.length + 1) {
            return;
        }
        if (ans.size() == nums.length) {
            res.add(new ArrayList<>(ans));
        }
        for (int i = 0; i < nums.length; i++) {
            if (!isHasUsedArr[i]) {
                ans.addLast(nums[i]);
                isHasUsedArr[i] = true;
                dfs(nums, i + 1, isHasUsedArr, ans, res);
                isHasUsedArr[i] = false;
                ans.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        Solution46 s = new Solution46();
        System.out.println(s.permute(new int[]{1, 2, 3}));
    }
}